﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Demo.Framework.DataStructure.Heap
{
    class Heap
    {
        private List<Node> _heap;
        public Heap(int[] elements)
        {
            _heap = new List<Node>();
            if (elements == null) { throw new Exception("Input array can not be null");}

            foreach (int item in elements)
            {
                Add(item);
            }              
            
        }

        public bool Add(int priority)
        {
            try
            {
                Node n = new Node(priority);
                _heap.Add(n);
                ShiftUp();
                return true;
            }
            catch (Exception)
            {
                
                throw;
            }
            
        }

        public object Remove(int priority)
        {
            try
            {
                object returnVal = _heap[0];
                int count = _heap.Count;
                _heap[0] = _heap[count];                               
                _heap.RemoveAt(count);
                
                ShiftDown();

                return returnVal;
                
            }
            catch (Exception)
            {
                
                throw;
            }
            return true;
        }
                
        // k -> 2p +1, 2p + 2
        private void ShiftUp()
        {
            int size = _heap.Count;
            int k = size - 1;

            while (k >0)
	        {
                int parent = (k - 1) / 2;
                if (_heap[parent].Value < _heap[k].Value)
                {
                    Node temp = _heap[parent];
                    _heap[parent] = _heap[k];
                    _heap[k] = temp;
                    k = parent;
                }
                else
                {
                    break;
                }
                         
	        }
        }

        private void ShiftDown()
        {
            int parent = 0;
            
            while (true)
            {
                int k1 = 2 * parent + 1;
                int k2 = 2 * parent + 1;
                int k = 0;

                if (k1 > _heap.Count)
                {
                    break;
                }
                else if (k2 > _heap.Count)
                {
                    k = k1;
                }
                else
                {
                    k = _heap[k1].Value == System.Math.Max(_heap[k1].Value, _heap[k2].Value) ? k1 : k2;
                }

                if (_heap[k].CompareTo(_heap[parent])>0)
                {
                    Node temp = _heap[parent];
                    _heap[parent] = _heap[k];
                    _heap[k] = temp;
                    parent = k;
                }                
            }
        }

        public override string ToString()
        {
            StringBuilder sb = new StringBuilder();
            
            for (int i = 0; i < _heap.Count; i++)
            {
                sb.Append(_heap[i].ToString());
            }

            return sb.ToString();
        }
    }
}
